package 每日一题;

import com.alibaba.fastjson.JSON;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-11-29
 **/

public class No438找到字符串中所有字母异位词 {

    /**
     * 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
     * 异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
     * <p>
     * 示例 1:
     * 输入: s = "cbaebabacd", p = "abc"
     * 输出: [0,6]
     * 解释:
     * 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
     * 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
     *  示例 2:
     * 输入: s = "abab", p = "ab"
     * 输出: [0,1,2]
     * 解释:
     * 起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
     * 起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
     * 起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
     *  
     * 提示:
     * 1 <= s.length, p.length <= 3 * 104
     * s 和 p 仅包含小写字母
     */

    public List<Integer> findAnagrams(String s, String p) {

        List<Integer> result = new ArrayList<>();

        if (s.length() < p.length()) {
            return result;
        }
        if (s.length() == p.length() && s.equals(p)) {
            result.add(0);
            return result;
        }

        // 不是子序列,而是异位词

        Set<Character> set = new HashSet<>();
        int[] countArr = new int[26];
        char[] bigArr = s.toCharArray();
        char[] smallArr = p.toCharArray();
        int count = 0;
        for (char c : smallArr) {
            set.add(c);
            if (countArr[c - 'a'] == 0) {
                count++;
            }
            countArr[c - 'a']++;
        }

        int left = 0;
        int right = 0;

        while (right < bigArr.length) {

            int c = bigArr[right];
            int index = c - 'a';

            countArr[index]--;

            // 当前字母置0了
            if (countArr[index] == 0) {
                count--;
            } else if (countArr[index] < 0) {
                // 小于0,那么left移动到等于0为止
                while (countArr[index] != 0 && left <= right) {
                    if (set.contains(bigArr[left]) && countArr[bigArr[left] - 'a']++ == 0) {
                        count++;
                    }
                    left++;
                }
            } else {
                // 还是大于0,就不管它
            }
            if (count == 0) {
                result.add(left);
            }

            right++;
        }

        return result;
    }

    public static void main(String[] args) {
        No438找到字符串中所有字母异位词 n = new No438找到字符串中所有字母异位词();
        List<Integer> result = n.findAnagrams("cbaebabacd", "abc");
        System.out.println(JSON.toJSONString(result));
    }

}
